Various types of non-volatile memory media may have limited endurance. Memory capacity may be lost as memory regions wear out. Mappings between logical and physical addresses for memory media may be changed over time so that repeated writes to a logical address do not cause undue wear at a single physical address. However, providing flexible wear leveling using an any-to-any mapping between a large number of logical addresses and a large number of physical addresses may involve maintaining large amounts of metadata.